'''
https://leetcode.cn/problems/sum-of-subarray-minimums/description/
'''
from collections import deque
from typing import List

class Solution:
    def sumSubarrayMins(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        # 所有子数组，他们分别的最小值，的和
        ans = 0
        stack = deque() # 栈中元素 大压小
        for i, num in enumerate(nums):
            while stack and num <= nums[stack[-1]]:
                cur = stack.pop()
                # nums[left], nums[right] < nums[cur]
                # left + 1, ... right - 1， 这段区间内，nums[cur]最小值
                left = stack[-1] if stack else -1
                right = i
                # 有多少子数组以我为最小值呢.
                ans += (cur - left) * (right - cur) * nums[cur] % MOD
            stack.append(i)
        while stack:
            cur = stack.pop()
            left = stack[-1] if stack else -1
            right = n
            ans += (cur - left) * (right - cur) * nums[cur] % MOD
        return ans % MOD
